Artur Czumaj Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick Coventry CV4 7AL United Kingdom Room:  CS.213 Phone: +44 24-7657-3796 Fax:      +44 24-7657-3024 E-mail: URL: http://www.dcs.warwick.ac.uk/~czumaj/

Publications

• Director of the Centre for Discrete Mathematics and its Applications (DIMAP)
• Member of the Division of Theory and Foundations (FoCS)


• Member of the Interest Group on Algorithmic Foundations of Information Technology (IGAFIT)


• I used to be the President of the European Association for Theoretical Computer Science (EATCS) (2020 - 2024)
• I used to be a member of the EATCS Council (2017 - 2024)


• I used to chair the LMS Computer Science Committee (until fall 2017)


• I'm also involved in some activities in the Alan Turing Institute, the Warwick Data Science Institute (WDSI) and the Warwick Centre for Doctoral Training in Mathematics of Real-world Systems (MathSys).

• My research is/was supported by EPSRC grants EP/D063191/1, EP/G064679/1, EP/G069034/1, EP/J021814/1, EP/N011163/1, EP/V01305X/1, EPSRC studentship, by the IBM Faculty Award, by the Royal Society International Exchanges Scheme, and by Weizmann-UK Making Connections Grants »Combinatorial and Algorithmic Primitives for Modern Networks« and »The Interplay between Algorithms and Randomness.«
  
  

• Information for Students: I have no summer internships!!! (and apologies for not responding to such email requests)

Events I am/was involved in organizing:

• 3rd IGAFIT Workshop for Algorithms Postdocs in Europe (AlgPiE by IGAFIT 2024), the International Conference and Research Center for Computer Science, Dagstuhl, Germany, September 16 – 20, 2024 (co-organized with Piotr Sankowski (University of Warsaw and IDEAS NCBR) and some post-docs (names to be confirmed later))
• Simons Institute Special Semester on Sublinear Algorithms, UC Berkeley, CA, USA, May 20 – August 9, 2024 (co-organized with Ronitt Rubinfeld (chair, MIT), Clément Canonne (University of Sydney), Piotr Indyk (MIT), Jelani Nelson (UC Berkeley), Noga Ron-Zewi (University of Haifa), and Asaf Shapira (Tel Aviv University))
• Workshop on Sublinear Graph Simplification, July 29 – August 2, 2024, Simons Institute for the Theory of Computing, UC Berkeley, CA, USA (co-organized with Mohsen Ghaffari (MIT), Sanjeev Khanna (University of Pennsylvania), Merav Parter (Weizmann Institute of Science), and Asaf Shapira (Tel Aviv University)), as a part of the Simons Institute Special Semester on Sublinear Algorithms, May 20 – August 9, 2024
• (PC chair of) Workshop on Local Algorithms (WOLA 2023), August 7 - 9, 2023, MIT, Cambridge, MA
• Computational Complexity Conference (CCC 2023), University of Warwick, July 17 - 20, 2023 (co-organized with Tom Gur (chair) and Sathyawageeswar Subramanian, all from the University of Warwick)
• Warwick-Weizmann Workshop 2023, Department of Computer Science and DIMAP, University of Warwick, May 1 - 4, 2023 (co-organized with Sayan Bhattacharya, Robert Krauthgamer, and Merav Parter)
• Weizmann-Warwick Workshop 2023, Department of Computer Science and Applied Mathematics, Weizmann Institute, February 26 - March 1, 2023 (co-organized with Sayan Bhattacharya, Robert Krauthgamer, and Merav Parter)
• DIMAP Theory Day 2022, University of Warwick, December 12, 2022 (co-organized with Tom Gur and Ramanujan Sridharan)
• Simons Semester on Algorithms for Massive Parallel Computation Model, IDEAS NCBR and Banach Center, Institute of Mathematics of the Polish Academy of Sciences, Warsaw, Poland, April – June, 2022 (co-organized with Piotr Sankowski (IDEAS NCBR & University of Warsaw) and Krzysztof Onak (Boston University))
• Workshop on Emerging Models of Colossal Computiation (E=mc²), Warsaw, Poland, May 16 — 18, 2022 (co-organized with Krzysztof Onak (Boston University), Piotr Sankowski (IDEAS NCBR & University of Warsaw), Martin Schulz (Technical University of Munich), and Jesper Larsson Träff (TU Wien))
• Workshop on Algorithmic Challenges of Big Data (ACBD 2022), Warsaw, Poland, May 9 — 10, 2022 (co-organized with Piotr Sankowski (IDEAS NCBR & University of Warsaw))
• The inaugural IGAFIT Workshop for Algorithms Postdocs in Europe (AlgPiE by IGAFIT 2019), Będlewo, Poland, October 14 - 18, 2019
• The 4th AlgoUK Workshop at the University of Warwick, September 17 - 18, 2019 (co-organized with Graham Cormode and Tom Gur)
• Warwick-Weizmann Workshop 2019, Department of Computer Science and DIMAP, University of Warwick, May 13 - 16, 2019 (co-organized with Sayan Bhattacharya, Robert Krauthgamer, and Merav Parter)
• DIMAP Workshop on Advances in Modern Graph Algorithms, April 8 - 11, 2019, Venice, Italy (coorganized with Sayan Bhattacharya, Matthias Englert, and Ramanujan Sridharan)
• Workshop on Sublinear Algorithms and Nearest-Neighbor Search, November 27 - 30, 2018, Simons Institute for the Theory of Computing, UC Berkeley, CA, USA (co-organized with Robert Krauthgamer (Weizmann Institute), Aarti Singh (Carnegie Mellon University), and Rachel A. Ward (University of Texas at Austin)), as a part of the Simons Institute Special Semester on Foundations of Data Science, August 15 - December 14, 2018
• Workshop on Data Summarization, University of Warwick, March 19 - 22, 2018 (co-organized with Graham Cormode)
• 10 Year Anniversary DIMAP Workshop, University of Warwick, December 11 - 13, 2017 (co-organized with Dan Kráľ)
• Workshop in Honour of Mike Paterson's 75th Birthday, University of Warwick, December 14, 2017 (co-organized with Dan Kráľ)
• Highlights of Algorithms 2017 (HALG 2017), Berlin, June 9 - 11, 2017
• Highlights of Algorithms 2016 (HALG 2016), Paris, June 6 - 8, 2016
• Alan Turing Institute scoping workshop on Distributed Machine Learning and Optimization, Edinburgh, November 25 - 27, 2015 (co-organized with Peter Richtarik (Edinburgh), Ilias Diakonikolas (Edinburgh), Raphael Hauser (Oxford), Mark Girolami (Warwick), John Shawe-Taylor (UCL)); (also here).
• Alan Turing Institute scoping workshop on Networks & Big Data, December 18, 2015 (co-organized with Patrick Wolfe (UCL), Natalia Bochkina (Edinburgh), Jon Crowcroft (Cambridge), Richard Gibbens (Cambridge), Peter Grindrod (Oxford), and Mark Handley (UCL))
• The London Mathematical Society 150th Anniversary Computer Science Colloquium (on Algorithms and Cryptography), The Royal Society, London, September 17, 2015 (co-organized with Faron Moller)
• 25th British Combinatorial Conference (BCC), University of Warwick, July 2015 (co-organized with Agelos Georgakopoulos, Dan Kráľ, Vadim Lozin, Oleg Pikhurko)
• 1st European Meeting on Algorithmic Challenges of Big Data (ACBD 2014), Warsaw, Poland, May 5 - 7, 2014 (co-organized with Aleksander Mądry and Piotr Sankowski)
• Big Data Analytics 2013, May 23 - 24, 2013, Microsoft Research, Cambridge, UK (co-organized with Milan Vojnovic and Jingren Zhou)
• Algorithmic Meeting, EPFL Lausanne, February 11 - 13, 2013 (co-organized with Aleksander Mądry)
• Weizmann-Warwick Workshop 2012, Eilat, Israel, September 10 - 13, 2012 (co-organized by Robert Krauthgamer, Uri Feige, and Matthias Englert)
• 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), University of Warwick, July 9 - 13, 2012.
• Warwick-Weizmann Workshop 2011, Department of Computer Science and DIMAP, University of Warwick, September 12 - 16, 2011 (co-organized by Amin Coja-Oghlan, Matthias Englert, Uri Feige, and Robert Krauthgamer).
• Workshop on Sublinear Algorithms, Bertinoro International Center for informatics, University of Bologna Residential Center Bertinoro (Forli), Italy, May 22 - 27, 2011 (co-organized by Piotr Indyk, Robert Krauthgamer, and Ronitt Rubinfeld).
• Weizmann-Warwick Workshop 2010, Weizmann Institute of Science, Israel, December 5 - 9, 2010 (co-organized by Amin Coja-Oghlan, Uri Feige, Robert Krauthgamer, and Harry Räcke).
• DIMAP Summer School on Approximation and Randomized Algorithms, DIMAP, University of Warwick, July 12 - 16, 2010 (co-organized with Matthias Englert and Harry Räcke).
• Dagstuhl seminar No. 08341 on »Sublinear Algorithms«, Dagstuhl Castle, Leibniz Center for Informatics, Germany, August 17 - 22, 2008 (co-organized with S. Muthukrishnan, R. Rubinfeld, and C. Sohler).
• »Mike66«, a workshop in honour of Professor Mike Paterson's 66th birthday, DIMAP, University of Warwick, September 18 - 19, 2008 (co-organized with Leslie Ann Goldberg and Uri Zwick).
• DIMAP Algorithms Day, DIMAP, University of Warwick, October 24, 2008 (co-organized with Matthias Englert, Oded Lachish, and Rahul Savani).
• 25th British Colloquium for Theoretical Computer Science (BCTCS), University of Warwick, April 6 - 9, 2009 (co-organized with Sara Kalvala and Steve Matthews).
• 3rd Workshop on »Flexible Network Design«, DIMAP, University of Warwick, UK, July 13 - 16, 2008 (co-organized with A. Gupta, S. Leonardi, R. Ravi, and H. Räcke).
• DIMAP Workshop on »Algorithmic Game Theory«, University of Warwick, UK, March 25 - 28, 2007.
• Workshop on »Algorithmic Graph Theory«, Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach, Germany, February 12 - 18, 2006 (co-organized by K. Jansen, F. Meyer auf der Heide, and I. Schiermeyer).
• Dagstuhl seminar No. 05291 on »Sublinear Algorithms«, Dagstuhl Castle, the International Conference and Research Center for Computer Science, Germany, July 17 - 22, 2005 (co-organized with S. Muthukrishnan, R. Rubinfeld, and C. Sohler).

• Draft of »Finding Cycles and Trees in Sublinear Time«, coauthored by O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler, manuscript, July 2010, arXive:1007.4230.
• Draft of »Testing Expansion in Bounded-Degree Graphs« © coauthored by Christian Sohler (FOCS'2007)
• Draft of »Small Space Representations for Metric Min-Sum k-Clustering and their Applications« © coauthored by Christian Sohler (Preliminary version appeared in STACS'2007)
• Draft of the full version of »Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs« © with Asaf Shapira and Christian Sohler. (Preliminary version appeared in SODA'2007)

• Draft of »Finding a heaviest triangle is not harder than matrix multiplication« © with Andrzej Lingas. (Preliminary version appeared in SODA'2007)
• Draft of a survey on sublinear-time algorithms © (coauthored by Christian Sohler) that appeared in Bulletin of the EATCS, 89: 23 - 47, June 2006.
• Draft of a paper »Faster algorithms for finding lowest common ancestors in directed acyclic graphs«, coauthored by Miroslaw Kowaluk and Andrzej Lingas, that appeared in Theoretical Computer Science, 380(1-2): 37 - 46, June 2007. (This paper combines my earlier draft Improved algorithms for the all-pairs lowest common ancestor problem in directed acyclic graphs (joint work with Andrzej Lingas) with ICALP 2005 paper LCA queries in directed acyclic graphs by Miroslaw Kowaluk and Andrzej Lingas.)
• Materials from the Dagstuhl seminar on Sublinear Algorithms that I (together with S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler) organized in July 2005. (A picture from the seminar.)
• Full version of the paper »Tight Bounds for Worst-Case Equilibria« (extended version of SODA'2002 paper, co-authored by B. Vöcking);
  this paper has been submitted to Journal of Algorithms in 2002, accepted there in 2003 ... and finally appeared in ... ACM Transactions on Algorithms, 3(1), February 2007.
• Drafts of full versions of two papers on property testing that have been published in conference proceedings long time ago:
  • Part I of ESA 2000 paper »Testing Convex Position«
  • Part II of ESA 2000 paper »Testing Euclidean Minimum Spanning Trees in the Plane«

---

• Some pictures from various conferences:
  • While attending a workshop in London, July 2018
  • Summer School in Warwick, July 2010; and another picture during excursion to Bletchley Park
  • RSA ...
  • ICALP 2009, enjoying Rhodes and its food, and giving a presentation
  • Mike 66, Workshop in Honour of Prof. Mike Paterson's 66th Birthday, September 2008; one more picture, and yet one more.
  • Dagstuhl 2008 (workshop "Sublinear Algorithms," August 2008) (workshop web page)
  • Group picture from Snowdonia and another picture
  • Dagstuhl 2007 (workshop "Probabilistic Methods in the Design and Analysis of Algorithms," September 2007) (workshop web page)
  • Dagstuhl 2007 (workshop "Computational Social Systems and the Internet," July 2007) (workshop web page)
  • DIMAP launch, March 2007
  • Dagstuhl 2005 (workshop "Sublinear Algorithms," July 2005) (workshop web page)
  • Dagstuhl 2005 (workshop "Design and Analysis of Randomized and Approximation Algorithms," May 2005) (workshop web page)
  • Dagstuhl 2005 (workshop "Computing and Markets," January 2005) (workshop web page)
  Bertinoro 2004 ("AGATE 2004, 1st Bertinoro Workshop on Algorithmic GAme ThEory," July 2004) - the fortress and the view and the castle
  • Oberwolfach 2004 (workshop "Approximation Algorithms for NP-Hard Problems," June 2004)
  • Braunwald (near Zurich - Andrzej R. is next to me and Alps are in the background) ... and another (group) picture
  • Dagstuhl 2003 (workshop "Algorithmic Game Theory and the Internet," June 2003)
  • Dagstuhl 2003 (another view)
  • Oberwolfach 2000 (workshop "Efficient Algorithms," August 2000)
  • RS&A conference in Poznan, August 1999 (bonfire, I'm sitting in 2nd row)
• Poznan, November 2010
• Power point presentation for the lectures given at the PIMS Summer School on Randomized Techniques for Combinatorial Algorithms, Simon Fraser University, August 2014.

Some of my PhD students (current and previous):

• Anna Adamaszek
• Michal Adamaszek
• Sam Coy (funded by EPSRC DTP)
• Peter Davies (recipient of the 2020 Warwick Faculty of Science, Engineering and Medicine Thesis Prize)
• Michail Fasoulakis
• Jan Hladky
• Wang Xin
• Hairong Zhao